|
Block sort, or block merge sort, is a sorting algorithm combining at least two merge operations with an insertion sort to arrive at O(n log n) in-place stable sorting. It gets its name from the observation that merging two sorted lists, A and B, is equivalent to breaking A into evenly sized ''blocks'', inserting each A block into B under special rules, and merging AB pairs. One practical algorithm for block sort was proposed by Pok-Son Kim and Arne Kutzner in 2008. == Overview == The outer loop of block sort is identical to a bottom-up merge sort, where each ''level'' of the sort merges pairs of subarrays, A and B, in sizes of 1, then 2, then 4, 8, 16, and so on, until both subarrays combined are the array itself. Rather than merging A and B directly as with traditional methods, a block-based merge algorithm divides A into discrete blocks of size (resulting in ''number'' of blocks as well), inserts each A block into B such that the first value of each A block is less than or equal to the B value immediately after it, then ''locally merges'' each A block with any B values between it and the next A block. As merges still require a separate buffer large enough to hold the A block to be merged, two areas within the array are reserved for this purpose (known as ''internal buffers''). The first two A blocks are thus modified to contain the first instance of each value within A, with the original contents of those blocks shifted over if necessary. The remaining A blocks are then inserted into B and merged using one of the two buffers as swap space. This process causes the values in that buffer to be rearranged. Once every A and B block of every A and B subarray have been merged for that level of the merge sort, the values in that buffer must be sorted to restore their original order, so an insertion sort must be applied. The values in the buffers are then redistributed to their first sorted position within the array. This process repeats for each level of the outer bottom-up merge sort, at which point the array will have been stably sorted. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Block sort」の詳細全文を読む スポンサード リンク
|